
package grafohamiltoniano; //probando

import java.io.IOException;
//import java.util.logging.Level;
//import java.util.logging.Logger;
import javax.swing.*;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.MouseEvent;
import java.awt.event.ActionListener;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
//import java.util.Random;
//import java.util.List;
//import java.util.ArrayList;
//import java.util.Iterator;
import java.util.Stack;
import java.io.File;

class Grafos extends JFrame {

    JButton botonVertices, botonAristas, botonMatriz, botonHallar, botonAyuda, botonAcerca, botonSalir, botonReiniciar, botonCargar, botonGuardar; //botones para elegir las acciones
    Lienzo lienzo = new Lienzo(); //tablero para pintar el grafo
    Font fuente = new Font("courier", Font.CENTER_BASELINE, 16); //Tipo de letra
    Color fondo = new Color(200, 200, 255); // Color de la ventana y de los paneles
    Container panel; //Contenedor para crear toda la ventana de la aplicacion
    Mensajes mensaje = new Mensajes();//Objeto utilizado para mostrar mensajes y la matriz
    int matGrafo[][];  //Representacion logica del grafo en una matriz de adyacencia
    int nVertices = 0;
    int nAristas = 0;
    int[] grados;
    boolean capturarVertices = false;
    boolean capturarAristas = false;
    private final JPanel panelcentral;
    Integer seleccionado;

//constructor para iniciar toda la parte grafica
    public Grafos() {
        super("--- G R A F O S ---"); //titulo de la ventana
        IniciarComponentes();

        panel = this.getContentPane();      //inicio panel principal
        panel.setLayout(new BorderLayout());//defino la forma como se ubican los componentes

        //Panel de la parte superior con la animacion
        JPanel panelsuperior = new JPanel();
        panelsuperior.add(new JLabel(new ImageIcon("Imagenes/Encabezado.gif")));
        panelsuperior.setBackground(fondo);
        panel.add(panelsuperior, BorderLayout.NORTH);

        //Panel que contiene el lienzo sobre el cual se va a pintar el grafo
        panelcentral = new JPanel();
        panelcentral.setLayout(new FlowLayout());
        panelcentral.add(lienzo);
        panelcentral.setBackground(fondo);
        panel.add(panelcentral, BorderLayout.CENTER);

        //Panes de la parte inferior
        JPanel panelinferior = new JPanel();
        panelinferior.setLayout(new GridLayout(2, 1));
        JLabel b, b2;
        panelinferior.add(b = new JLabel("TEORIA DE REDES", JLabel.CENTER));
        panelinferior.add(b2 = new JLabel("UNIVERSIDAD DE ANTIOQUIA 2011-1", JLabel.CENTER));
        b.setFont(fuente);
        b2.setFont(fuente);
        panelinferior.setBackground(fondo);
        panel.add(panelinferior, BorderLayout.SOUTH);

        // Panel que contiene los botones para las diferentes acciones
        JPanel paneloriente = new JPanel();
        paneloriente.setLayout(new GridLayout(2, 1));
        JPanel panelorientearriba = new JPanel();//Subpanel con los botones
        panelorientearriba.setLayout(new GridLayout(10, 1));
        panelorientearriba.add(botonVertices);
        panelorientearriba.add(botonAristas);
        botonAristas.setEnabled(false);
        panelorientearriba.add(botonMatriz);
        botonMatriz.setEnabled(false);
        panelorientearriba.add(botonHallar);
        botonHallar.setEnabled(false);
        panelorientearriba.add(botonAyuda);
        panelorientearriba.add(botonAcerca);
        panelorientearriba.add(botonCargar);
        panelorientearriba.add(botonGuardar);
        panelorientearriba.add(botonReiniciar);
        panelorientearriba.add(botonSalir);
        panelorientearriba.setBackground(fondo);

        JPanel panelorienteabajo = new JPanel(); //subpanes con una animacion del grafo
        panelorienteabajo.setBackground(fondo);
        panelorienteabajo.add(new JLabel(new ImageIcon("Imagenes/Grafo.gif")));

        paneloriente.add(panelorientearriba);
        paneloriente.add(panelorienteabajo);
        panel.add(paneloriente, BorderLayout.EAST);

        setLocation(12, 12); //ubicacion de la ventana
        setResizable(false); //Para que no se le pueda cambiar el tamaño a la ventana
        setSize(1000, 700); //tamaño
        setVisible(true); // hago la ventana visible
        setDefaultCloseOperation(EXIT_ON_CLOSE);//esta linea hace que la aplicacion se destruya cuando cierro la ventana
        //DEFINO LAS PROPIEDADES DE LA VENTANA DE EJECUCION
    }

    private void cargarGrafo() {
        try {
                JFileChooser fd = new JFileChooser("./");
		fd.setApproveButtonText("Abrir solo .grf"); //Texto del boton de abrir
		fd.addChoosableFileFilter(new FiltroTxt()); //Cargo el filtro para mostrar solo los .txt
		fd.setDialogTitle("Seleccione el Archivo 1 que desea Cargar"); //titulo de la ventana
		fd.showOpenDialog(null); //Hago que el dialogo se muestre

                File archivo=fd.getSelectedFile();
                System.out.println(archivo);
		if(archivo.exists()){
                    ObjectInputStream in = new ObjectInputStream(new FileInputStream(archivo));
                     Lienzo l = (Lienzo) in.readObject();
                    panelcentral.remove(lienzo);
                    lienzo = l;

                    panelcentral.add(lienzo);
                    lienzo.paint(lienzo.getGraphics());
                    in.close();
                    capturarVertices = false;
                    capturarAristas = true;
                    botonAristas.setEnabled(false);
                    botonMatriz.setEnabled(true);
                    botonHallar.setEnabled(true);
                    nVertices = lienzo.getNVertices();
                    nAristas = lienzo.getNAristas();
                    grados = lienzo.getGrados();
                    matGrafo = new int[nVertices][nVertices];
                    for (Arista ar : lienzo.aristas) {
                        Vertice v1 = ar.v1;
                        Vertice v2 = ar.v2;
                        matGrafo[v1.RetornaNumeroVertice()][v2.RetornaNumeroVertice()] = 1;
                        matGrafo[v2.RetornaNumeroVertice()][v1.RetornaNumeroVertice()] = 1;
                    }

                }
                else
                    mensaje.MostrarMensajeAtencion("EL ARCHIVO QUE TRATA DE ABRIR NO EXISTE");


            
        } catch (ClassNotFoundException ex) {
        } catch (IOException ex) {
        }
    }

   /* private void cargarGrafo() {
        try {
            ObjectInputStream in = new ObjectInputStream(new FileInputStream("./grafo.grf"));
            Lienzo l = (Lienzo) in.readObject();
            panelcentral.remove(lienzo);
            lienzo = l;

            panelcentral.add(lienzo);
            lienzo.paint(lienzo.getGraphics());
            in.close();
            capturarVertices = false;
            capturarAristas = true;
            botonAristas.setEnabled(false);
            botonMatriz.setEnabled(true);
            botonHallar.setEnabled(true);
            nVertices = lienzo.getNVertices();
            nAristas = lienzo.getNAristas();
            grados = lienzo.getGrados();
            matGrafo = new int[nVertices][nVertices];
            for (Arista ar : lienzo.aristas) {
                Vertice v1 = ar.v1;
                Vertice v2 = ar.v2;
                matGrafo[v1.RetornaNumeroVertice()][v2.RetornaNumeroVertice()] = 1;
                matGrafo[v2.RetornaNumeroVertice()][v1.RetornaNumeroVertice()] = 1;
            }
        } catch (ClassNotFoundException ex) {
        } catch (IOException ex) {
        }
    }*/

    private void guardarGrafo() {
        if (lienzo.aristas.size() > 1) {
            String nombre =JOptionPane.showInputDialog(null,"Como desea llamar el Grafo","NOMBRE",  JOptionPane.QUESTION_MESSAGE);	
            nombre=nombre+".grf";
            try {
                    lienzo.setNVertices(nVertices);
                    lienzo.setNAristas(nAristas);
                    lienzo.setGrados(grados);
                    ObjectOutputStream out = new ObjectOutputStream(new FileOutputStream("./"+nombre));
                    out.writeObject(lienzo);
                    out.close();
                    mensaje.MostrarMensajeInformacion("El grafo "+nombre+" fue Guardado","Servicio de Guardado");
             } catch (IOException ex) {
                    mensaje.MostrarMensajeError("Ocurrio un error al Guargar el Grafo");
                }
            
        }
    }

    /*private void guardarGrafo() {
        if (lienzo.aristas.size() > 1) {
            if (JOptionPane.showConfirmDialog(null, "Desea reemplazar el grafo anterior?", "REEMPLAZO DE ARCHIVO", JOptionPane.YES_NO_OPTION) == JOptionPane.YES_OPTION) {

                try {
                    lienzo.setNVertices(nVertices);
                    lienzo.setNAristas(nAristas);
                    lienzo.setGrados(grados);
                    ObjectOutputStream out = new ObjectOutputStream(new FileOutputStream("./grafo.grf"));
                    out.writeObject(lienzo);
                    out.close();
                } catch (IOException ex) {
                    mensaje.MostrarMensajeError("Ocurrio un error al Guargar el Grafo");
                }
            }
        }
    }*/

    //
    public void IniciarComponentes() {
        botonVertices = new JButton("Dibujar Vertices");
        botonAristas = new JButton("Dibujar Aristas");
        botonMatriz = new JButton("Mostrar Matriz");
        botonHallar = new JButton("Es Hamiltoniano?");
        botonAyuda = new JButton("Ayuda");
        botonAcerca = new JButton("Acerca de ...");
        botonSalir = new JButton("Salida");
        botonReiniciar = new JButton("Volver a Empezar");
        botonCargar = new JButton("Cargar Grafo");
        botonGuardar = new JButton("Guardar Grafo");

        botonAristas.addActionListener(new ActionListener() {

            public void actionPerformed(ActionEvent evt) {
                OyenteBotonAristas();
            }
        });
        botonVertices.addActionListener(new ActionListener() {

            public void actionPerformed(ActionEvent evt) {
                OyenteBotonVertices();
            }
        });
        botonMatriz.addActionListener(new ActionListener() {

            public void actionPerformed(ActionEvent evt) {
                OyenteBotonMatriz();
            }
        });
        botonHallar.addActionListener(new ActionListener() {

            public void actionPerformed(ActionEvent evt) {
                OyenteBotonHallar();
            }
        });
        botonAyuda.addActionListener(new ActionListener() {

            public void actionPerformed(ActionEvent evt) {
                JOptionPane.showMessageDialog(null, new ImageIcon("Imagenes/Ayuda.png"), "--- AYUDA DE GRAFOS ---", JOptionPane.PLAIN_MESSAGE);
            }
        });
        botonAcerca.addActionListener(new ActionListener() {

            public void actionPerformed(ActionEvent evt) {
                JOptionPane.showMessageDialog(null, new ImageIcon("Imagenes/Acerca.png"), "--- ACERCA DE GRAFOS ---", JOptionPane.PLAIN_MESSAGE);
            }
        });
        botonSalir.addActionListener(new ActionListener() {

            public void actionPerformed(ActionEvent evt) {
                System.exit(0);
            }
        });
        botonReiniciar.addActionListener(new ActionListener() {

            public void actionPerformed(ActionEvent evt) {
                Limpiar();
            }
        });
        botonCargar.addActionListener(new ActionListener() {

            public void actionPerformed(ActionEvent evt) {
                cargarGrafo();
            }
        });
        botonGuardar.addActionListener(new ActionListener() {

            public void actionPerformed(ActionEvent evt) {
                guardarGrafo();
            }
        });
        //se adicionan los escuchas para cuando se pulsen los botones

        lienzo.setSize(700, 520); //tamaño del lienzo
        //lienzo.setBackground(fondoClaro);
        lienzo.addMouseListener(new java.awt.event.MouseAdapter() {

            public void mousePressed(MouseEvent e) {
                OyenteLienzo(e);
            }
        });

    }

//Acciones a realizar cuando se pulse el boton de crear
    public void OyenteBotonVertices() {
        mensaje.MostrarMensajeInformacion("De click donde quiere insertar todos los vertices", "INSERTAR VERTICES");
        capturarVertices = true;
        botonVertices.setEnabled(false);
        botonAristas.setEnabled(true);
    }

//Acciones a realizar cuando se pulse el boton de crear	aristas
    public void OyenteBotonAristas() {
        if (nVertices > 2) {
            matGrafo = new int[nVertices][nVertices];
            mensaje.MostrarMensajeInformacion("De click sobre dos vertices", "INSERTAR ARISTAS");
            capturarVertices = false;
            capturarAristas = true;
            botonAristas.setEnabled(false);
            botonMatriz.setEnabled(true);
            botonHallar.setEnabled(true);
        } else {
            mensaje.MostrarMensajeAtencion("No hay suficientes vertices, Inserte mas");
        }
    }

//Muestra una lista con todos los vertices para que se elija uno que sera el destino
    public void OyenteBotonMatriz() {
        capturarAristas = true;
        mensaje.MostrarMensajeInformacion("numero de vertices " + nVertices + "\n" + "numero de aristas " + nAristas, "SUMARIO");
        mensaje.MostrarTabla(matGrafo);
    }

//Este metodo ejecuta el algoritmo para saber si es o no hamiltoniano
    public void OyenteBotonHallar() {
        boolean esHamiltoniano = false;
        capturarAristas = false;
        CalcularGrados();
        //busquedaExahustiva();
        //condiciones suficientes
        if (proposicion453()) {
            esHamiltoniano = true;
            mensaje.MostrarMensajeInformacion("El grafo es Hamiltoniano por la proposicion 4.5.3\nTodos sus vertices tienen grado >= n/2", "GRAFO HAMILTONIANO");
        }

        if (proposicion454()) {
            esHamiltoniano = true;
            mensaje.MostrarMensajeInformacion("El grafo es Hamiltoniano por la proposicion 4.5.4\nTiene al menos 1/2(n-1)(n-2)+2 aristas", "GRAFO HAMILTONIANO");
        }

        if (proposicion455()) {
            esHamiltoniano = true;
            mensaje.MostrarMensajeInformacion("El grafo es Hamiltoniano por la proposicion 4.5.5\nLa suma de grados de vertices no adyacentes es >= n", "GRAFO HAMILTONIANO");
        }

        //condiciones necesarias vertice de corte
        if (proposicion459()) {
            esHamiltoniano = false;
        }
         else{
            //busqueda Heuristica y Exahustiva
            if (busquedaHeuristica()) {
              esHamiltoniano = true;
           }
            else {
               if (busquedaExahustiva()) {
                   esHamiltoniano = true;
                   //el mismo metodo se encarga de mostrar el resultado
                }
            }
         }

        

        if (!esHamiltoniano) {
            mensaje.MostrarMensajeInformacion("NO ES HAMILTONIANO", "GRAFO HAMILTONIANO");
        }
        lienzo.repaint();
    }

//
    public void Limpiar() {
        capturarVertices = false;
        capturarAristas = false;
        botonMatriz.setEnabled(false);
        botonHallar.setEnabled(false);
        botonVertices.setEnabled(true);
        botonAristas.setEnabled(false);
        nVertices = 0;
        nAristas = 0;
        lienzo.Limpiar(lienzo.getGraphics());
    }

//
    public void OyenteLienzo(MouseEvent ev) {
        if (capturarVertices) {
            Vertice v = new Vertice(ev.getPoint(), nVertices);
            lienzo.AgregarPunto(v);
            nVertices++;
            lienzo.paint(lienzo.getGraphics());
        }//fin capturar vertices
        if (capturarAristas) {
            Vertice v = new Vertice(ev.getPoint());
            int seleccionado = lienzo.ExisteVertice(v);

            if (seleccionado != -1) {
                if (lienzo.HaySeleccionado()) {
                    Vertice v1 = lienzo.RetornaSeleccionado();
                    Vertice v2 = lienzo.RetornaVertice(seleccionado);
                    Arista arista = new Arista(v1, v2);
                    lienzo.AgregarArista(arista);
                    lienzo.DesSeleccionarVertice();

                    matGrafo[v1.RetornaNumeroVertice()][v2.RetornaNumeroVertice()] = 1;
                    matGrafo[v2.RetornaNumeroVertice()][v1.RetornaNumeroVertice()] = 1;
                    nAristas++;
                } else {
                    lienzo.SeleccionarVertice(seleccionado);
                }
            }
            lienzo.paint(lienzo.getGraphics());
        }//fin capturar aristas
    }

//
    public void CalcularGrados() {
        grados = new int[nVertices];
        for (int i = 0; i < nVertices; i++) {
            for (int j = 0; j < nVertices; j++) {
                grados[j] += matGrafo[i][j];
            }
        }

        /*for(int i=0;i<nVertices;i++)
        nAristas+=grados[i];
        
        nAristas=nAristas/2; //Calculo el numero de aristas como grados/2
         */
    }

//==============================================================================
//Condiciones suficientes
//proposicion 4.5.3
    public boolean proposicion453() {
        boolean res = true;
        for (int i = 0; i < nVertices; i++) {
            if (grados[i] < (float)nVertices / 2) {
                res = false;
            }
        }
        return (res);
    }

//proposicion 4.5.4
    public boolean proposicion454() {
        if (nAristas >= (((nVertices - 1) * (nVertices - 2) / 2) + 2)) {
            return (true);
        } else {
            return (false);
        }
    }

//proposicion 4.5.5
    public boolean proposicion455() {
        boolean res = true;
        for (int i = 0; i < nVertices; i++) {
            int j = i + 1;
            while (j < nVertices) {
                if (matGrafo[i][j] == 0) {
                    if (grados[i] + grados[j] < nVertices) {
                        res = false;
                        i = nVertices;
                        j = nVertices; //equivale a break
                    }
                }
                j++;
            }
        }

        return (res);
    }

//==============================================================================
//Condiciones necesarias
    int[] val = new int[nVertices + 100];

    public boolean proposicion459() {
        boolean res = false;

        int k;
        //Elimina cada uno de los vertices para verificar si es un vertice corte.
        for (int i = 0; i <= nVertices - 1; i++) {
            for (k = 0; k <= nVertices - 1; k++) {//inicializa el vector val en 0
                val[k] = 0;
            }

            val[i] = 1; //Asigna un 1 al vector que se ha eliminado para marcarlo como ya visitado y que no interfiera en el resultado.
            k = 1;

            if (k != i) //pregunta si el primer vector es diferente al vector a verificar
            {
                visitar(k, i);//Llamada al metodo recursivo
            } else { //Si el primer vector es el mismo vector a verificar pasamos al siguiente vector y ejecutamos la llamada recursiva.
                k = k + 1;
                visitar(k, i);
            }

            for (int j = 0; j <= nVertices - 1; j++) {//Recorre el vector val
                if (val[j] == 0) { //si algun elemento del vector val es igual a 0, quiere decir que ese vector no fue visitado por la llamada recursiva y por lo tanto el grafo resultante no es conexo
                    res = true; //Por lo tanto el vertice que se estaba verificando es un vertice corte.
                    i = i + 1;
                    mensaje.MostrarMensajeInformacion("El vertice " + i + " es un punto de corte\nEl grafo no es hamiltoniano por proposicion 4.5.9", "GRAFO NO HAMILTONIANO");
                    return (res);
                    //break;
                }
            }
        }
        return (res);
    }

    // Algoritmo recursivo para recorrer la matriz y llenar el vector val
    void visitar(int k, int i) {
        int t;
        val[k] = 1;//Marca la posicion del vector con 1 para indicar que ya fue visitado.

        for (t = 0; t <= nVertices - 1; t++)//Recorre la matriz de adyacencia
        {
            if (t != i) {//obvia el vector que se esta verificando
                if (matGrafo[k][t] == 1 && val[t] == 0) {
                    visitar(t, i);//verifica que entre los dos vectores sean adyacentes y que no se halla visitado aun,
                }        //si las condiciones se cumplen hace un llamado recursivo a visitar con el parametro t.
            }
        }
    }

//==============================================================================
//Busqueda Heuristica
//metodo que realiza una busqueda heuristica para ver si existe un camino hamiltoniano
    private boolean busquedaHeuristica() {
        Grafo G1 = new Grafo();
        Grafo G2 = new Grafo();

        boolean encontrado = false;
        int tempIterator = 0;
        int temp2 = 0;
        int a = -1;
        int b = -1;
        int c = -1;
        int d = -1;
        int pastC = -1;
        int prev = -1;
        int cur = -1;
        int next = -1;


        for (int i = 0; i < matGrafo.length; i++) {
            for (int j = 0; j < matGrafo.length; j++) {
                if (matGrafo[i][j] == 1) {
                    G1.adicionaArista(i + 1, j + 1);
                }
            }
        }

        //Construye un circuito en el grafo G2
        for (int i = 1; i < nVertices; i++) {
            G2.adicionaArista(i, i + 1);
        }

        G2.adicionaArista(nVertices, 1);

        //Elimina arista que no estan en G1
        //Busca la primer arista en G2 (1,2)
        prev = 0;
        cur = 1;
        next = 2;
        tempIterator = 0; //Numero de aristas examinadas y potencialmente fijadas

        while (tempIterator < nVertices) {
            a = cur;
            b = next;
            if ((G1.ExisteArista(a, b)) == false) { //Necesita fijarse
                pastC = b;
                int busquedaC = 0;
                for (int offset = 0; offset < (nVertices - 1); offset++) {
                    busquedaC++;

                    if (busquedaC == nVertices) {
                        return false;
                    }

                    c = (pastC + offset) % nVertices + 1;

                    //revisa si esta arista es la siguiente en el circuito
                    if (c != a && c != b && c != prev && (G2.ExisteArista(c, pastC))) { //Si es la siguiente
                        pastC = c; //Si esto no funciona como un c, por lo menos continúa de él
                        offset = -1;
                    } else { //no es la siguiente
                        continue;
                    }


                    if ((G1.ExisteArista(a, c)) == false) {//si la arista no se puede usar entonces continua
                        continue;
                    } else {
                        //intenta encontrar d
                        for (int offset2 = 0; offset2 < (nVertices - 1); offset2++) {
                            d = (c + offset2) % nVertices + 1;
                            if (c != d && d != b && d != a && (G2.ExisteArista(d, c))) {
                                //este es el unico posible
                                break;
                            }
                        } //fin del for (buscando d)
                        if ((G1.ExisteArista(d, b))) {//busca c & d!
                            break;
                        }
                    }
                } //fin del for (buscando c)

                next = c;
                //remover (a,b) y (c,d); y adicionar (a,c) y (b,d).
                G2.adicionaArista(a, c);
                G2.adicionaArista(b, d);
                G2.EliminaArista(c, d);
                G2.EliminaArista(a, b);
            } //fin busqueda
            else {
                //std::printf("Edge (%d, %d) was fine!",a,b); //debug
            }


            //el "next" sigue siendo "b" (ninguna se fijo), o si se cambio a " c " (si se fijo).
            //en el For del proximo ciclo , el cur necesita tomar en el valor de next
            //y el nuevo "next" necesita escogerse.
            prev = cur;
            cur = next;
            for (int offset = 0; offset < (nVertices - 1); offset++) {
                next = (cur + offset) % nVertices + 1;
                if (next != prev && (G2.ExisteArista(cur, next))) {
                    //encontro es siguiente
                    break;
                }
            }
            tempIterator++;
        } //fin while


        String resultado = "";

        //Retorna la ruta
        mensaje.MostrarMensajeInformacion("El grafo es Hamiltoniano segun la busqueda Heuristica", "GRAFO HAMILTONIANO");

        //busca la primer arista
        encontrado = false;
        tempIterator = 2;
        while (!encontrado) {
            if ((G2.ExisteArista(1, tempIterator))) {
                encontrado = true;
                cur = 1;
                next = tempIterator;
                resultado = resultado + "1, ";
                resultado = resultado + tempIterator;
            }
            tempIterator++;
            if (tempIterator > nVertices) {
                mensaje.MostrarMensajeAtencion("Hubo un problema, No se tomo el primer vertice");
                return false;
            }
        }

        //guarda las demas aristas
        while (next != 1) {
            prev = cur;
            cur = next;
            for (int offset = 0; offset < (nVertices - 1); offset++) {
                next = (cur + offset) % nVertices + 1;
                if (next != prev && (G2.ExisteArista(cur, next))) {
                    resultado = resultado + ", ";
                    resultado = resultado + next;
                    break;
                }
            }

            //busaca errores
            if (cur == next) {
                String str = "";
                str = "Hubo un problema, No hay arista luego del " + cur + " excepto " + prev;
                mensaje.MostrarMensajeAtencion(str);
                return false;
            }
        }
        mensaje.MostrarMensajeInformacion(" CAMINO HAMILTONIANO ENCONTRADO HEURISTICAMENTE: " + resultado, "GRAFO HAMILTONIANO");

        if (JOptionPane.showConfirmDialog(null, "DESEA VER EL CICLO", "CICLO HAMILTONIANO", JOptionPane.OK_CANCEL_OPTION, JOptionPane.QUESTION_MESSAGE) == JOptionPane.OK_OPTION) {
            lienzo.PintarCiclo(resultado);
        }

        return true;
    }

    //Busqueda exahustiva
    public boolean busquedaExahustiva() {
        Grafo G1 = new Grafo();

        for (int i = 0; i < matGrafo.length; i++) {
            for (int j = 0; j < matGrafo.length; j++) {
                if (matGrafo[i][j] == 1) {
                    G1.adicionaArista(i + 1, j + 1);
                }
            }
        }

        Stack<Integer> pila = new Stack<Integer>();
        Stack<Integer> pilaFor = new Stack<Integer>();
        int size = matGrafo.length;
        boolean existe = false;

        for (int i = 1; i <= matGrafo.length; i++) {

            if (pila.contains(i) & i < size) {

                continue;
            } else {
                if (pila.contains(i)) {
                    int rr = 1;
                    pila.pop();
                    i = pilaFor.pop() + 1;
                }
            }

            if (pila.isEmpty() || G1.ExisteArista(pila.peek(), i)) {
                if (!pila.contains(i)) {
                    pila.push(i);
                    System.out.println(pila);
                    if (pila.size() == size) {
                        if (G1.ExisteArista(pila.firstElement(), pila.lastElement())) {
                            existe = true;
                            break;
                        } else {
                            pila.pop();
                        }
                    } else {
                        pilaFor.push(i);
                        i = 0;
                    }
                }
            }
            if (i >= matGrafo.length & !pilaFor.isEmpty()) {
                while (i >= size & !pilaFor.isEmpty()) {
                    pila.pop();
                    i = pilaFor.pop();
                }
            }
        }



        if (existe) {
            pila.push(pila.firstElement());
            mensaje.MostrarMensajeInformacion(" CAMINO HAMILTONIANO ENCONTRADO EXAHUSTIVAMENTE: " + pila.toString(), "GRAFO HAMILTONIANO");
            String resultado = pila.toString();
            resultado = resultado.substring(1, resultado.length() - 1);
            if (JOptionPane.showConfirmDialog(null, "DESEA VER EL CICLO", "CICLO HAMILTONIANO", JOptionPane.OK_CANCEL_OPTION, JOptionPane.QUESTION_MESSAGE) == JOptionPane.OK_OPTION) {
                lienzo.PintarCiclo(resultado);
            }
            return true;
        }

        return false;

    }


    class FiltroTxt extends javax.swing.filechooser.FileFilter{

    final static String grf= "grf";

    public FiltroTxt(){}

    public boolean accept(File f){
        if(f.isDirectory()){
            return true;
        }
        String s = f.getName();
        int i=s.lastIndexOf('.');
        if(i>0 && i<s.length()-1){
            String extension = s.substring(i+1).toLowerCase();
            if (grf.equals(extension))
            	return true;
            else
                return false;
        }
        return false;
    }

    public String getDescription(){
        return "Archivos .grf";//aparecera en las opciones de escoger tipo de archivo para abrir
    }
}


//Metodo main para iniciar la aplicacion
    public static void main(String args[]) {
        new Grafos();//Construyo la aplicacion por medio de un objeto de este tipo
    }
}

